Product Code Database
In cryptography, a timing attack is a side-channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms. Every logical operation in a computer takes time to execute, and the time can differ based on the input; with precise measurements of the time for each operation, an attacker may be able to work backwards to the input.
Information can leak from a system through measurement of the time it takes to respond to certain queries. How much this information can help an attacker depends on many variables such as cryptographic system design, the CPU running the system, the algorithms used, assorted implementation details, timing attack countermeasures, the accuracy of the timing measurements. Any algorithm that has data-dependent timing variation is vulnerable to timing attacks. Removing timing-dependencies is difficult since varied execution time can occur at any level.
Vulnerability to timing attacks is often overlooked in the design phase and can be introduced unintentionally with compiler optimizations. Countermeasures include blinding and constant-time functions.
The data-dependency of timing may stem from one of the following:
In 2003, Dan Boneh and David Brumley demonstrated a practical network-based timing attack on SSL-enabled web servers, based on a different vulnerability having to do with the use of RSA with Chinese remainder theorem optimizations. The actual network distance was small in their experiments, but the attack successfully recovered a server private key in a matter of hours. This demonstration led to the widespread deployment and use of blinding techniques in SSL implementations. In this context, blinding is intended to remove correlations between key and encryption time.David Brumley and Dan Boneh. Remote timing attacks are practical. USENIX Security Symposium, August 2003.
Some versions of Unix use a relatively expensive implementation of the crypt library function for hashing an 8-character password into an 11-character string. On older hardware, this computation took a deliberately and measurably long time: as much as two or three seconds in some cases. The login program in early versions of Unix executed the crypt function only when the login name was recognized by the system. This leaked information through timing about the validity of the login name, even when the password was incorrect. An attacker could exploit such leaks by first applying brute-force to produce a list of login names known to be valid, then attempt to gain access by combining only these names with a large set of passwords known to be frequently used. Without any information on the validity of login names the time needed to execute such an approach would increase by orders of magnitude, effectively rendering it useless. Later versions of Unix have fixed this leak by always executing the crypt function, regardless of login name validity.
Two otherwise securely isolated processes running on a single system with either cache memory or virtual memory can communicate by deliberately causing and/or in one process, then monitoring the resulting changes in access times from the other. Likewise, if an application is trusted, but its paging/caching is affected by branching logic, it may be possible for a second application to determine the values of the data compared to the branch condition by monitoring access time changes; in extreme examples, this can allow recovery of cryptographic key bits.See Percival, Colin, Cache Missing for Fun and Profit, 2005.Bernstein, Daniel J., Cache-timing attacks on AES, 2005.
The 2017 Meltdown and Spectre attacks which forced CPU manufacturers (including Intel, AMD, ARM, and IBM) to redesign their CPUs both rely on timing attacks. As of early 2018, almost every computer system in the world is affected by Spectre.
In 2018, many internet servers were still vulnerable to slight variations of the original timing attack on RSA, two decades after the original vulnerability was discovered.
const char *ca = a, *cb = b;
for (size_t i = 0; i < length; i++)
if (ca[i] != cb[i])
return false;
return true;
}
By comparison, the following version runs in constant-time by testing all characters and using a bitwise operation to accumulate the result:
const char *ca = a, *cb = b;
bool result = true;
for (size_t i = 0; i < length; i++)
result &= ca[i] == cb[i];
return result;
}
In the world of C library functions, the first function is analogous to , while the latter is analogous to NetBSD's or OpenBSD's and . On other systems, the comparison function from cryptographic libraries like OpenSSL and libsodium can be used.
|
|
